package com.cat.chapter053;
import java.util.Arrays;

/**
 * @author cat
 * @description https://leetcode.cn/problems/remove-duplicate-letters/
 * @create 2025/7/24 15:19
 * @since JDK17
 */

public class Solution02 {
    static int N = 26;
    static char[] stack = new char[N];
    static boolean[] enter = new boolean[N];
    static int[] cnt = new int[N];

    public String removeDuplicateLetters(String str) {
        Arrays.fill(enter, false);
        Arrays.fill(cnt, 0);
        int r = 0;
        char[] s = str.toCharArray();
        for (char c : s) {
            cnt[c - 'a']++;
        }

        for (char cur : s) {
            if (enter[cur - 'a'] == false) { // 没有在栈中
                while (r > 0 && stack[r - 1] > cur && cnt[stack[r - 1] - 'a'] > 0) {
                    enter[stack[--r] - 'a'] = false;
                }
                stack[r++] = cur;
                enter[cur - 'a'] = true;
            }
            cnt[cur - 'a']--;
        }

        return String.valueOf(stack, 0, r);
    }
}


